#pragma once
#include <iostream>
#include <assert.h>

using std::cout;
using std::endl;

namespace key
{
    template<class K>
    class BSTreeNode
    {
        public:
            K _key;
            BSTreeNode* _left;
            BSTreeNode* _right;

            BSTreeNode(const K& key)
                : _key(key)
                , _left(nullptr)
                , _right(nullptr)
            {}

        private:
    };

    template<class K>
    class BSTree
    {
        private:
            using BSNode = BSTreeNode<K>;
            BSNode* _root = nullptr;
        
        protected:
            void _inOrder(BSNode* root)
            {
                if(!root)
                {
                    return;
                }
                
                _inOrder(root->_left);
                cout<<root->_key<<" ";
                _inOrder(root->_right);           
            }

            void Destory(BSNode* root)
            {
                if(!_root)
                    return;
                Destory(root->_left);
                Destory(root->_right);
                delete root;
            }
        public:
            BSTree()
                :_root(nullptr)
            {}
            
            ~BSTree()
            {
                Destory(_root);
                _root = nullptr;
            }
            bool insert(const K& val)
            {
                if(!_root)
                {
                    BSNode * newnode = new BSNode(val);
                    _root = newnode;
                    return true;
                }

                // 左边小于根, 右边大于根, 不允许重复的值出现
                BSNode* parent = nullptr;
                BSNode* cur = _root;
                while(cur)
                {
                    if(val < cur->_key)
                    {
                        parent = cur;
                        cur = cur->_left;
                    }
                    else if(val > cur->_key)
                    {
                        parent = cur;
                        cur = cur->_right;
                    }
                    else
                        return false;
                }
                cur = new BSNode(val);
                if(val < parent->_key)
                {
                    parent->_left = cur;
                }
                else{
                    parent->_right = cur;
                }
                return true;
            }

            void inOrder()
            {
                _inOrder(_root);
                cout<<endl;
            }

            bool find(const K& val) const
            {
                if(!_root) return false;
                BSNode* cur = _root;
                while(cur)
                {
                    if(val < cur->_key)
                    {
                        cur = cur->_left;
                    }
                    else if(val > cur->_key)
                    {
                        cur = cur->_right;
                    }
                    else
                    {
                        return true;
                    }
                }
                return false;
            }

            bool erase(const K& val)
            {
                // if(!_root) return false;
                BSNode* parent = nullptr;
                BSNode* cur = _root;

                while(cur)
                {
                    if(val < cur->_key)
                    {
                        parent = cur;
                        cur = cur->_left;
                    }
                    else if(val > cur->_key)
                    {
                        parent = cur;
                        cur = cur->_right;
                    }
                    else
                    {
                        break;
                    }
                }
                if(!cur) return false; // no match val

                // 情况1：有两个子节点
                if(cur->_left && cur->_right)
                {
                    // 找右子树的最小节点（或左子树的最大节点）
                    BSNode* replace = cur->_right;
                    BSNode* replace_parent = cur;
                    while(replace->_left)
                    {
                        replace_parent = replace;
                        replace = replace->_left;
                    }
                    
                    // 交换值
                    cur->_key = replace->_key;
                    // 转为删除replace节点（它最多有一个右子节点）
                    cur = replace;
                    parent = replace_parent;
                }
                
                // 情况2和3：有0或1个子节点
                BSNode* child = cur->_left ? cur->_left : cur->_right;
                
                if(!parent) // 删除的是根节点
                {
                    _root = child;
                }
                else
                {
                    if(parent->_left == cur)
                        parent->_left = child;
                    else
                        parent->_right = child;
                }
                
                delete cur;
                return true;
            }
    };
}



// 字典键值对
namespace key_value
{
    template<class K, class V>
    class BSTreeNode
    {
        public:
            K _key;
            V _val;
            BSTreeNode<K, V>* _left;
            BSTreeNode<K, V>* _right;

            BSTreeNode(const K& key, const V& val)
                : _key(key)
                , _val(val)
                , _left(nullptr)
                , _right(nullptr)
            {}

        private:
    };

    template<class K, class V>
    class BSTree
    {
        private:
            using BSNode = BSTreeNode<K, V>;
            BSNode* _root = nullptr;
        
        protected:
            void _inOrder(BSNode* root)
            {
                if(!root)
                {
                    return;
                }
                
                _inOrder(root->_left);
                cout<<root->_key<<": "<<root->_val<<" ";
                _inOrder(root->_right);           
            }

            void Destory(BSNode* root)
            {
                if(!root)
                    return;
                Destory(root->_left);
                Destory(root->_right);
                delete root;
            }
            
            BSNode* _copy(const BSNode* src)
            {
                if(!src)
                    return nullptr;
                BSNode* newroot = new BSNode(src->_key, src->_val);
                newroot->_left = _copy(src->_left);
                newroot->_right = _copy(src->_right);
                return newroot;
            }

        public:
            BSTree() = default;

            BSTree(const BSTree& bstree)
            {
                _root = _copy(bstree._root);
            }
            BSTree& operator=(BSTree tmp)
            {
                std::swap(_root, tmp._root);
                return *this;
            }

            V& operator[](const K& key)
            {
                BSNode* node = find(key);
                if(node)
                {
                    return node->_val;
                }
                else
                {
                    throw std::out_of_range("Key not found in BSTree");
                }
            }
            ~BSTree()
            {
                Destory(_root);
                _root = nullptr;
            }
            bool insert(const K& key, const V& val)
            {
                if(!_root)
                {
                    BSNode * newnode = new BSNode(key, val);
                    _root = newnode;
                    return true;
                }

                // 左边小于根, 右边大于根, 不允许重复的值出现
                BSNode* parent = nullptr;
                BSNode* cur = _root;
                while(cur)
                {
                    if(key < cur->_key)
                    {
                        parent = cur;
                        cur = cur->_left;
                    }
                    else if(key > cur->_key)
                    {
                        parent = cur;
                        cur = cur->_right;
                    }
                    else
                        return false;
                }
                cur = new BSNode(key, val);
                if(key < parent->_key)
                {
                    parent->_left = cur;
                }
                else{
                    parent->_right = cur;
                }
                return true;
            }

            void inOrder()
            {
                _inOrder(_root);
                cout<<endl;
            }

            BSNode* find(const K& key) const
            {
                BSNode* cur = _root;
                while(cur)
                {
                    if(key < cur->_key)
                    {
                        cur = cur->_left;
                    }
                    else if(key > cur->_key)
                    {
                        cur = cur->_right;
                    }
                    else
                    {
                        return cur;
                    }
                }
                return nullptr;
            }

            bool erase(const K& key)
            {
                BSNode* parent = nullptr;
                BSNode* cur = _root;

                while(cur)
                {
                    if(key < cur->_key)
                    {
                        parent = cur;
                        cur = cur->_left;
                    }
                    else if(key > cur->_key)
                    {
                        parent = cur;
                        cur = cur->_right;
                    }
                    else
                    {
                        break;
                    }
                }
                if(!cur) return false; // no match key

                // 情况1：有两个子节点
                if(cur->_left && cur->_right)
                {
                    // 找右子树的最小节点（或左子树的最大节点）
                    BSNode* replace = cur->_right;
                    BSNode* replace_parent = cur;
                    while(replace->_left)
                    {
                        replace_parent = replace;
                        replace = replace->_left;
                    }
                    
                    // 交换值
                    cur->_key = replace->_key;
                    // 转为删除replace节点（它最多有一个右子节点）
                    cur = replace;
                    parent = replace_parent;
                }
                
                // 情况2和3：有0或1个子节点
                BSNode* child = cur->_left ? cur->_left : cur->_right;
                
                if(!parent) // 删除的是根节点
                {
                    _root = child;
                }
                else
                {
                    if(parent->_left == cur)
                        parent->_left = child;
                    else
                        parent->_right = child;
                }
                
                delete cur;
                return true;
            }
    };
}